package euler.p101_150;

import java.util.Arrays;

import euler.MainEuler;
import euler.helper.NaturalHelper;

public class Euler104 extends MainEuler {

    /*
        The Fibonacci sequence is defined by the recurrence relation:

            F(n) = F(n−1) + F(n−2),
            where F(1) = 1 and F(2) = 1.

        It turns out that F(541), which contains 113 digits, is the first
        Fibonacci number for which the last nine digits are 1-9 pandigital
        (contain all the digits 1 to 9, but not necessarily in order).
        And F(2749), which contains 575 digits, is the first Fibonacci number
        for which the first nine digits are 1-9 pandigital.

        Given that F(k) is the first Fibonacci number for which the first
        nine digits AND the last nine digits are 1-9 pandigital, find k.

     */
    public String resolve() {

        int limiteMenos = 1000000000;
        long limiteMas = 1000000000000000l;
        int reducirMas = 1000000;

        int fn_2_menos = 1;
        int fn_1_menos = 1;
        int fn_menos;

        long fn_2_mas = 1;
        long fn_1_mas = 1;
        long fn_mas = 0;

        double golden = (1+Math.sqrt(5))/2;

        int i = 2;
        boolean terminar = false;
        boolean tooBig = false;

        int[] numerosInt = new int[]{1,2,3,4,5,6,7,8,9};

        while (!terminar) {
            i++;

            fn_menos = (fn_1_menos + fn_2_menos) % limiteMenos;
            fn_2_menos = fn_1_menos;
            fn_1_menos = fn_menos;

            if (!tooBig) {
                fn_mas = fn_1_mas + fn_2_mas;
                fn_2_mas = fn_1_mas;
                fn_1_mas = fn_mas;

                tooBig = fn_mas > limiteMas;
            } else {
                fn_mas = (long)(golden*fn_mas);
                if (fn_mas > limiteMas) {
                    fn_mas/=10;
                }
            }

            int[] digitosInt = NaturalHelper.digitos((int)fn_menos, 10, true);
            Arrays.sort(digitosInt);

            if (Arrays.equals(digitosInt, numerosInt)) {
                digitosInt = NaturalHelper.digitos((int)(fn_mas/reducirMas), 10, true);
                Arrays.sort(digitosInt);
                terminar = Arrays.equals(digitosInt, numerosInt);
            }
        }

        return String.valueOf(i);
        // 329468
    }

}
